package tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 652. 寻找重复的子树
 *
 * 给定一棵二叉树 root，返回所有重复的子树。
 * 对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 * 如果两棵树具有相同的结构和相同的结点值，则它们是重复的。
 */
public class FindDuplicateSubtrees_652 {
    List<TreeNode> res = new ArrayList<>();
    // hashmap保存每个序列出现的次数，当当前出现的序列已出现时说明重复了，就加入结果集
    HashMap<String, Integer> map = new HashMap<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traversal(root);
        return res;
    }

    // 将二叉树中的每一个节点的字符串形式存储在map中，直接判断出现的次数
    private String traversal(TreeNode root) {
        if (root == null) {
            return "#";
        }

        // 前序遍历！！！
        String left = traversal(root.left);
        String right = traversal(root.right);
        String str = left + "," + right + "," + root.val;
        int count = map.getOrDefault(str, 0) + 1;
        if (count == 2) {
            res.add(root);
        }
        map.put(str, count);
        return str;
    }
}
